package com.fw.leetcode.recursion;

import com.fw.leetcode.LeetCode;

/**
 * 21. Merge Two Sorted Lists
 *
 * You are given the heads of two sorted linked lists list1 and list2.
 * Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
 * Return the head of the merged linked list.
 *
 * Example 1:
 *  Input: list1 = [1,2,4], list2 = [1,3,4]
 *  Output: [1,1,2,3,4,4]
 *
 * Example 2:
 *  Input: list1 = [], list2 = []
 *  Output: []
 *
 * Example 3:
 *  Input: list1 = [], list2 = [0]
 *  Output: [0]
 *
 * Constraints:
 *  The number of nodes in both lists is in the range [0, 50].
 *  -100 <= Node.val <= 100
 *  Both list1 and list2 are sorted in non-decreasing order.
 */
public class Num_0021 implements LeetCode {
    private interface Solution extends LinkedList {
        ListNode mergeTwoLists(ListNode list1, ListNode list2);

        default void assertExpected(int[] list1, int[] list2, int[] expected) {
            if (!assertEquals(mergeTwoLists(build(list1), build(list2)), build(expected))) {
                mergeTwoLists(build(list1), build(list2));
            }
        }
    }

    private static class MyRecursionSolution implements Solution {

        @Override
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 其次：递归：时O(n+m) 空O(n+m)
            /*
             * 合并两个排序单链表
             *  [1,2,3,4,5]
             *  [3,5]
             */
            if (list1 == null) return list2;
            if (list2 == null) return list1;
            ListNode head;
            if (list1.val < list2.val) {
                head = list1;
                head.next = mergeTwoLists(list1.next, list2);
            } else {
                head = list2;
                head.next = mergeTwoLists(list2.next, list1);
            }
            return head;
        }
    }

    private static class MySolution implements Solution {

        @Override
        public ListNode mergeTwoLists(ListNode list1, ListNode list2) { // 最优：双指针：时O(n+m) 空O(1)
            /*
             * 合并两个排序单链表
             *  [1,2,3,4,5]
             *  [3,5]
             */
            ListNode header = new ListNode(-1); //辅助头节点
            ListNode cur = header;
            while (list1 != null && list2 != null) {
                if (list1.val < list2.val) { // 优先把小的先入队
                    cur.next = list1;
                    list1 = list1.next;
                } else {
                    cur.next = list2;
                    list2 = list2.next;
                }
                cur = cur.next;
            }
            cur.next = list1 != null ? list1 : list2; // 连接剩余链表
            return header.next;
        }
    }

    public static void main(String[] args) {
        Solution solution = new MyRecursionSolution();
        solution.assertExpected(new int[]{1,2,4}, new int[]{1,3,4}, new int[]{1,1,2,3,4,4});
        solution.assertExpected(new int[]{}, new int[]{}, new int[]{});
        solution.assertExpected(new int[]{}, new int[]{0}, new int[]{0});
    }
}
